package leetcode3;

public class Day11 {





    public int LastRemaining_Solution (int n, int m) {
        // write code here
        int[] dp = new int[n+1];
        for(int i=2;i<=n;i++) {
            dp[i] = (dp[i-1]+m)%i;
        }
        return dp[n];
    }


    /**
     * 大数加法
     *
     */
    public String solve (String s, String t) {
        // write code here
        //1.从字符串末尾开始遍历
        //2.使用变量记录两个“字母”相加的值
        //3.使用新的字符串记录结果
        int is=s.length()-1,it=t.length()-1;
        int tmp=0;
        StringBuilder ret = new StringBuilder();
        while(is>=0 || it>=0 || tmp>0) {
            if(is>=0) tmp += s.charAt(is--)-'0';
            if(it>=0) tmp += (int)t.charAt(it--)-'0';
            ret.append((char)(tmp%10+'0'));
            tmp /= 10;
        }

        return ret.reverse().toString();
    }


    /**
     * 大数相乘
     * @param ss
     * @param tt
     * @return
     */
    public String solve2 (String ss, String tt) {
        // write code here
        char[] s = new StringBuilder(ss).reverse().toString().toCharArray();
        char[] t = new StringBuilder(tt).reverse().toString().toCharArray();
        int m = s.length,n = t.length;
        int[] tmp = new int[m+n];
        for(int i=0;i<m;i++) { //固定一个数
            for(int j=0;j<n;j++) {
                tmp[i+j] += (s[i]-'0') * (t[j]-'0');
            }
        }
        //处理进位
        int k=0;
        StringBuilder ret = new StringBuilder();
        for(int x:tmp) {
            k += x;
            ret.append((char)(k%10+'0'));
            k/=10;
        }

        while (k!=0) {
            ret.append((char)(k%10)+'0');
            k/=10;
        }
        while (ret.length() >1 && ret.charAt(ret.length()-1)=='0') {
            ret.deleteCharAt(ret.length()-1);
        }

        return ret.reverse().toString();
    }
}
